package 链表;

public class leetcode_链表 {
    /**
     * 237.删除链表中的节点
     * https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
     * 
     */
    public void deleteNode(ListNode node) {
        node = node.next;
    }

    /**
     * 206 链表翻转
     *  https://leetcode-cn.com/problems/reverse-linked-list/
     */
    public ListNode reverseList(ListNode head) {
        
        if (head == null || head.next == null) return head;
        ListNode tmpHead = head;
        ListNode newHead = null;
        
        while (tmpHead != null) {
            ListNode tmp = tmpHead.next;
            tmpHead.next = newHead;
            newHead = tmpHead;
            tmpHead = tmp;
        }
        return newHead;
    }
    public ListNode reverseList1(ListNode head) { // 递归实现
        
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
    /**
     * 876. 链表的中间结点
     * https://leetcode-cn.com/problems/middle-of-the-linked-list/
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode low = head;
        ListNode fast = head;
        while (fast.next == null) { // 如果就只有一个节点 返回当前节点
            return low;
        }
        while(fast.next != null) { // 快指针 下一个节点不为空 
            if (fast.next.next != null) { // 能调到下一步
                fast = fast.next.next; // 快 走两步
                low = low.next; // 慢 走一步
            } else { // 否则 元素个数为 偶数个, 返回 慢指针的 下一个节点
                return low.next;
            }
        }
        return low; // 返回慢指针指向的节点
    }

    /***
     * 21. 合并两个有序链表
     * https://leetcode-cn.com/problems/merge-two-sorted-lists/
     */

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        return mergeTwoLists2(l1, l2);
    }
    /**
     * 递归实现
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    /** 
     * 非递归实现
     */
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        ListNode tmp = new ListNode(0);

        ListNode res = tmp;

        while(l1.next != null && l2.next != null) {
            if (l1.val <= l2.val) {
                tmp.next = l1;
                l1 = l1.next;
            } else {
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        
        if (l1.next == null) {
            tmp.next = l2;
        }  
        if (l2.next == null) {
            tmp.next = l1;
        }
        return res.next;
    }

    /**
     * 160. 相交链表
     * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode tmpA = headA;
        ListNode tmpB = headB;

        while (tmpA != tmpB) {
            tmpA = tmpA == null ? headB:tmpA.next;
            tmpB = tmpB == null ? headA:tmpB.next;
            System.out.println(tmpA);
            System.out.println(tmpB);
        }
        
        return tmpA;
    }

    /**
     * 83. 删除排序链表中的重复元素
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == cur.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
    /**
     * 141. 环形链表
     * https://leetcode-cn.com/problems/linked-list-cycle/
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null&&fast.next.next != null) {
            fast = fast.next;
            if (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 203. 移除链表元素
     * https://leetcode-cn.com/problems/remove-linked-list-elements/
     */
    public ListNode removeElements(ListNode head, int val) {
        
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode cur = res;
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return res.next;
    }

    /**
     * 234. 回文链表
     * https://leetcode-cn.com/problems/palindrome-linked-list/
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        // 找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 翻转 前半部分的节点

        ListNode prev = null;
        ListNode next = null;
        while (head != slow) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }

        // 如果 是 奇数个 去掉后半部分的第一个节点
        if (fast != null) {
            slow = slow.next;
        }
        
        while (prev != null) {
            if (prev.val != slow.val) {
                return false;
            }
            prev = prev.next;
            slow = slow.next;
        }

        return true;
    }

    


}